home *** CD-ROM | disk | FTP | other *** search
/ Amiga Tools 2 / Amiga Tools 2.iso / tools / packer / ha0999beta / src / asc.c < prev    next >
C/C++ Source or Header  |  1995-03-09  |  10KB  |  443 lines
  1. /***********************************************************************
  2.   This file is part of HA, a general purpose file archiver.
  3.   Copyright (C) 1995 Harri Hirvola
  4.  
  5.   This program is free software; you can redistribute it and/or modify
  6.   it under the terms of the GNU General Public License as published by
  7.   the Free Software Foundation; either version 2 of the License, or
  8.   (at your option) any later version.
  9.  
  10.   This program is distributed in the hope that it will be useful,
  11.   but WITHOUT ANY WARRANTY; without even the implied warranty of
  12.   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13.   GNU General Public License for more details.
  14.  
  15.   You should have received a copy of the GNU General Public License
  16.   along with this program; if not, write to the Free Software
  17.   Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  18. ************************************************************************
  19.     HA ASC method
  20. ***********************************************************************/
  21.  
  22. /* #include <malloc.h> */
  23. #include <stdlib.h>
  24. #include <stdio.h>
  25. #include "ha.h"
  26. #include "haio.h"
  27. #include "asc.h"
  28. #include "swdict.h"
  29. #include "acoder.h"
  30. #include "error.h"
  31.  
  32. #define POSCODES 31200
  33. #define SLCODES    16
  34. #define LLCODES 48
  35. #define LLLEN    16
  36. #define LLBITS    4
  37. #define LLMASK    (LLLEN-1)
  38. #define LENCODES (SLCODES+LLCODES*LLLEN)
  39. #define LTCODES (SLCODES+LLCODES)
  40. #define CTCODES 256
  41. #define PTCODES 16
  42. #define LTSTEP 8
  43. #define MAXLT (750*LTSTEP)
  44. #define CTSTEP 1
  45. #define MAXCT (1000*CTSTEP)
  46. #define PTSTEP 24
  47. #define MAXPT (250*PTSTEP) 
  48. #define TTSTEP 40
  49. #define MAXTT (150*TTSTEP)
  50. #define TTORD 4
  51. #define TTOMASK (TTORD-1);
  52. #define LCUTOFF (3*LTSTEP)
  53. #define CCUTOFF (3*CTSTEP)
  54. #define CPLEN 8
  55. #define LPLEN 4
  56. #define MINLENLIM 4096
  57.  
  58. static U16B ltab[2*LTCODES];
  59. static U16B eltab[2*LTCODES];
  60. static U16B ptab[2*PTCODES];
  61. static U16B ctab[2*CTCODES];
  62. static U16B ectab[2*CTCODES];
  63. static U16B ttab[TTORD][2];
  64. static U16B ccnt,pmax,npt;
  65. static U16B ces;
  66. static U16B les;
  67. static U16B ttcon;
  68.  
  69. void asc_cleanup(void) {
  70.     
  71.     swd_cleanup();
  72. }
  73.  
  74. static void tabinit(U16B t[], U16B tl, U16B ival) {
  75.  
  76.     register U16B i,j;
  77.     
  78.     for (i=tl;i<2*tl;++i) t[i]=ival;
  79.     for (i=tl-1,j=(tl<<1)-2;i;--i,j-=2) {
  80.     t[i]=t[j]+t[j+1];
  81.     }
  82. }
  83.  
  84. static void tscale(U16B t[], U16B tl) {
  85.  
  86.     register U16B i,j;
  87.     
  88.     for (i=(tl<<1)-1;i>=tl;--i) {
  89.     if (t[i]>1) t[i]>>=1;
  90.     }
  91.     for (i=tl-1,j=(tl<<1)-2;i;--i,j-=2) {
  92.     t[i]=t[j]+t[j+1];
  93.     }
  94. }
  95.  
  96. static void tupd(U16B t[], U16B tl, U16B maxt, U16B step, U16B p) {
  97.  
  98.     register S16B i;
  99.     
  100.     for (i=p+tl;i;i>>=1) t[i]+=step;
  101.     if (t[1]>=maxt) tscale(t,tl);
  102. }
  103.  
  104. static void tzero(U16B t[], U16B tl, U16B p) {
  105.  
  106.     register S16B i,step;
  107.     
  108.     for (i=p+tl,step=t[i];i;i>>=1) t[i]-=step;
  109. }
  110.  
  111. static void model_init(void) {
  112.  
  113.     register S16B i;
  114.     
  115.     ces=CTSTEP;
  116.     les=LTSTEP;
  117.     ccnt=0;
  118.     ttcon=0;
  119.     npt=pmax=1;
  120.     for (i=0;i<TTORD;++i) ttab[i][0]=ttab[i][1]=TTSTEP;
  121.     tabinit(ltab,LTCODES,0);
  122.     tabinit(eltab,LTCODES,1);
  123.     tabinit(ctab,CTCODES,0);
  124.     tabinit(ectab,CTCODES,1);
  125.     tabinit(ptab,PTCODES,0);    
  126.     tupd(ptab,PTCODES,MAXPT,PTSTEP,0);
  127. }
  128.  
  129. static void pack_init(void) {
  130.     
  131.     model_init();
  132.     ac_init_encode();
  133. }
  134.  
  135. static void unpack_init(void) {
  136.  
  137.     model_init();
  138.     ac_init_decode();
  139. }
  140.  
  141. static void ttscale(U16B con) {
  142.  
  143.     ttab[con][0]>>=1;
  144.     if (ttab[con][0]==0) ttab[con][0]=1;
  145.     ttab[con][1]>>=1;
  146.     if (ttab[con][1]==0) ttab[con][1]=1;
  147. }
  148.  
  149. static void codepair(S16B l, S16B p) {
  150.  
  151.     register U16B i,j,lt,k,cf,tot;
  152.     
  153.     i=ttab[ttcon][0]+ttab[ttcon][1];
  154.     ac_out(ttab[ttcon][0],i,i+1);
  155.     ttab[ttcon][1]+=TTSTEP;
  156.     if (i>=MAXTT) ttscale(ttcon);
  157.     ttcon=((ttcon<<1)|1)&TTOMASK;
  158.     while (ccnt>pmax) {
  159.     tupd(ptab,PTCODES,MAXPT,PTSTEP,npt++);
  160.     pmax<<=1;    
  161.     }
  162.  
  163.     for (i=p,j=0;i;++j,i>>=1); 
  164.     cf=ptab[PTCODES+j];
  165.     tot=ptab[1];
  166.     for (lt=0,i=PTCODES+j;i;i>>=1) {
  167.     if (i&1) lt+=ptab[i-1];
  168.     ptab[i]+=PTSTEP;
  169.     }
  170.     if (ptab[1]>=MAXPT) tscale(ptab,PTCODES);
  171.     ac_out(lt,lt+cf,tot);
  172.     if (p>1) {
  173.     for (i=0x8000U;!(p&i);i>>=1);
  174.     j=p&~i;
  175.     if (i!=(pmax>>1)) ac_out(j,j+1,i);
  176.     else ac_out(j,j+1,ccnt-(pmax>>1));
  177.     }
  178.     i=l-MINLEN;
  179.     if (i==LENCODES-1) i=SLCODES-1,j=0xffff;
  180.     else if (i<SLCODES-1) j=0xffff; 
  181.     else {
  182.     j=(i-SLCODES+1)&LLMASK;
  183.     i=((i-SLCODES+1)>>LLBITS)+SLCODES;    
  184.     }
  185.     if ((cf=ltab[LTCODES+i])==0) {
  186.     ac_out(ltab[1],ltab[1]+les,ltab[1]+les);    
  187.     for (lt=0,k=LTCODES+i;k;k>>=1) {
  188.         if (k&1) lt+=eltab[k-1];
  189.         ltab[k]+=LTSTEP;
  190.     }
  191.     if (ltab[1]>=MAXLT) tscale(ltab,LTCODES);
  192.     ac_out(lt,lt+eltab[LTCODES+i],eltab[1]);
  193.     tzero(eltab,LTCODES,i);
  194.     if (eltab[1]!=0) les+=LTSTEP;
  195.     else les=0;
  196.     for (k=i<=LPLEN?0:i-LPLEN;
  197.          k<(i+LPLEN>=LTCODES-1?LTCODES-1:i+LPLEN);++k) {
  198.         if (eltab[LTCODES+k]) tupd(eltab,LTCODES,MAXLT,1,k);
  199.     }
  200.     }
  201.     else {
  202.     tot=ltab[1]+les;
  203.     for (lt=0,k=LTCODES+i;k;k>>=1) {
  204.         if (k&1) lt+=ltab[k-1];
  205.         ltab[k]+=LTSTEP;
  206.     }
  207.     if (ltab[1]>=MAXLT) tscale(ltab,LTCODES);
  208.     ac_out(lt,lt+cf,tot);
  209.     }
  210.     if (ltab[LTCODES+i]==LCUTOFF) les-=LTSTEP<les?LTSTEP:les-1; 
  211.     if (j!=0xffff) ac_out(j,j+1,LLLEN); 
  212.     if (ccnt<POSCODES) {
  213.     ccnt+=l;
  214.     if (ccnt>POSCODES) ccnt=POSCODES;
  215.     }
  216. }
  217.  
  218.  
  219. static void codechar(S16B c) {
  220.  
  221.     register U16B i,lt,tot,cf;
  222.  
  223.     i=ttab[ttcon][0]+ttab[ttcon][1];
  224.     ac_out(0,ttab[ttcon][0],i+1);
  225.     ttab[ttcon][0]+=TTSTEP;
  226.     if (i>=MAXTT) ttscale(ttcon);
  227.     ttcon=(ttcon<<1)&TTOMASK;
  228.     if ((cf=ctab[CTCODES+c])==0) {
  229.     ac_out(ctab[1],ctab[1]+ces,ctab[1]+ces);
  230.     for (lt=0,i=CTCODES+c;i;i>>=1) {
  231.         if (i&1) lt+=ectab[i-1];
  232.         ctab[i]+=CTSTEP;
  233.     }
  234.     if (ctab[1]>=MAXCT) tscale(ctab,CTCODES);
  235.     ac_out(lt,lt+ectab[CTCODES+c],ectab[1]);
  236.     tzero(ectab,CTCODES,c);
  237.     if (ectab[1]!=0) ces+=CTSTEP;
  238.     else ces=0;
  239.     for (i=c<=CPLEN?0:c-CPLEN;
  240.          i<(c+CPLEN>=CTCODES-1?CTCODES-1:c+CPLEN);++i) {
  241.         if (ectab[CTCODES+i]) tupd(ectab,CTCODES,MAXCT,1,i);
  242.     }
  243.     }
  244.     else {
  245.     tot=ctab[1]+ces;
  246.     for (lt=0,i=CTCODES+c;i;i>>=1) {
  247.         if (i&1) lt+=ctab[i-1];
  248.         ctab[i]+=CTSTEP;
  249.     }
  250.     if (ctab[1]>=MAXCT) tscale(ctab,CTCODES);
  251.     ac_out(lt,lt+cf,tot);
  252.     }
  253.     if (ctab[CTCODES+c]==CCUTOFF) ces-=CTSTEP<ces?CTSTEP:ces-1; 
  254.     if (ccnt<POSCODES) ++ccnt;
  255. }
  256.  
  257.  
  258. void asc_pack(void) {
  259.     
  260.     S16B oc;
  261.     U16B omlf,obpos;
  262.     
  263.     swd_init(LENCODES+MINLEN-1,POSCODES);
  264.     pack_init();
  265.     for (swd_findbest();swd_char>=0;) {
  266.     if (swd_mlf>MINLEN || (swd_mlf==MINLEN && swd_bpos<MINLENLIM)) {
  267.         omlf=swd_mlf;
  268.         obpos=swd_bpos;
  269.         oc=swd_char;
  270.         swd_findbest();
  271.         if (swd_mlf>omlf) codechar(oc);
  272.         else {
  273.         swd_accept();
  274.         codepair(omlf,obpos);
  275.         swd_findbest();
  276.         }
  277.     }
  278.     else {
  279.         swd_mlf=MINLEN-1;
  280.         codechar(swd_char);
  281.         swd_findbest();
  282.     }
  283.     }
  284.     ac_out(ttab[ttcon][0]+ttab[ttcon][1],
  285.        ttab[ttcon][0]+ttab[ttcon][1]+1,ttab[ttcon][0]+ttab[ttcon][1]+1);
  286.     ac_end_encode();
  287.     asc_cleanup();
  288. }
  289.  
  290.  
  291. void asc_unpack(void) {
  292.     
  293.     register U16B l,p,tv,i,lt;
  294.     
  295.     swd_dinit(POSCODES);
  296.     unpack_init();
  297.     for (;;) {
  298.     tv=ac_threshold_val(ttab[ttcon][0]+ttab[ttcon][1]+1);        
  299.     i=ttab[ttcon][0]+ttab[ttcon][1];
  300.     if (ttab[ttcon][0]>tv) {
  301.         ac_in(0,ttab[ttcon][0],i+1);
  302.         ttab[ttcon][0]+=TTSTEP;
  303.         if (i>=MAXTT) ttscale(ttcon);
  304.         ttcon=(ttcon<<1)&TTOMASK;
  305.         tv=ac_threshold_val(ctab[1]+ces);
  306.         if (tv>=ctab[1]) {
  307.         ac_in(ctab[1],ctab[1]+ces,ctab[1]+ces);
  308.         tv=ac_threshold_val(ectab[1]);
  309.         for (l=2,lt=0;;) {
  310.             if (lt+ectab[l]<=tv) {
  311.             lt+=ectab[l];
  312.             ++l;
  313.             }
  314.             if (l>=CTCODES) {
  315.             l-=CTCODES;
  316.             break;
  317.             }
  318.             l<<=1;
  319.         }
  320.         ac_in(lt,lt+ectab[CTCODES+l],ectab[1]);
  321.         tzero(ectab,CTCODES,l);
  322.         if (ectab[1]!=0) ces+=CTSTEP;
  323.         else ces=0;
  324.         for (i=l<CPLEN?0:l-CPLEN;
  325.              i<(l+CPLEN>=CTCODES-1?CTCODES-1:l+CPLEN);++i) {
  326.             if (ectab[CTCODES+i]) tupd(ectab,CTCODES,MAXCT,1,i);
  327.         }
  328.         }
  329.         else {
  330.         for (l=2,lt=0;;) {
  331.             if (lt+ctab[l]<=tv) {
  332.             lt+=ctab[l];
  333.             l++;
  334.             }
  335.             if (l>=CTCODES) {
  336.             l-=CTCODES;
  337.             break;
  338.             }
  339.             l<<=1;
  340.         }
  341.         ac_in(lt,lt+ctab[CTCODES+l],ctab[1]+ces);
  342.         }
  343.         tupd(ctab,CTCODES,MAXCT,CTSTEP,l);
  344.         if (ctab[CTCODES+l]==CCUTOFF) ces-=CTSTEP<ces?CTSTEP:ces-1; 
  345.         swd_dchar(l);
  346.         if (ccnt<POSCODES) ++ccnt;
  347.     }
  348.     else if (i>tv) {
  349.         ac_in(ttab[ttcon][0],i,i+1);
  350.         ttab[ttcon][1]+=TTSTEP;
  351.         if (i>=MAXTT) ttscale(ttcon);
  352.         ttcon=((ttcon<<1)|1)&TTOMASK;
  353.         while (ccnt>pmax) {
  354.         tupd(ptab,PTCODES,MAXPT,PTSTEP,npt++);
  355.         pmax<<=1;    
  356.         }
  357.         tv=ac_threshold_val(ptab[1]);
  358.         for (p=2,lt=0;;) {
  359.         if (lt+ptab[p]<=tv) {
  360.             lt+=ptab[p];
  361.             p++;
  362.         }
  363.         if (p>=PTCODES) {
  364.             p-=PTCODES;
  365.             break;
  366.         }
  367.         p<<=1;
  368.         }
  369.         ac_in(lt,lt+ptab[PTCODES+p],ptab[1]);
  370.         tupd(ptab,PTCODES,MAXPT,PTSTEP,p);
  371.         if (p>1) {
  372.         for (i=1;p;i<<=1,--p);
  373.         i>>=1;
  374.         if (i==(pmax>>1)) l=ccnt-(pmax>>1);
  375.         else l=i;
  376.         p=ac_threshold_val(l);
  377.         ac_in(p,p+1,l);
  378.         p+=i;
  379.         }
  380.         tv=ac_threshold_val(ltab[1]+les);
  381.         if (tv>=ltab[1]) {
  382.         ac_in(ltab[1],ltab[1]+les,ltab[1]+les);
  383.         tv=ac_threshold_val(eltab[1]);
  384.         for (l=2,lt=0;;) {
  385.             if (lt+eltab[l]<=tv) {
  386.             lt+=eltab[l];
  387.             ++l;
  388.             }
  389.             if (l>=LTCODES) {
  390.             l-=LTCODES;
  391.             break;
  392.             }
  393.             l<<=1;
  394.         }
  395.         ac_in(lt,lt+eltab[LTCODES+l],eltab[1]);
  396.         tzero(eltab,LTCODES,l);
  397.         if (eltab[1]!=0) les+=LTSTEP;
  398.         else les=0;
  399.         for (i=l<LPLEN?0:l-LPLEN;
  400.              i<(l+LPLEN>=LTCODES-1?LTCODES-1:l+LPLEN);++i) {
  401.             if (eltab[LTCODES+i]) tupd(eltab,LTCODES,MAXLT,1,i);
  402.         }
  403.         }
  404.         else {
  405.         for (l=2,lt=0;;) {
  406.             if (lt+ltab[l]<=tv) {
  407.             lt+=ltab[l];
  408.             ++l;
  409.             }
  410.             if (l>=LTCODES) {
  411.             l-=LTCODES;
  412.             break;
  413.             }
  414.             l<<=1;
  415.         }
  416.         ac_in(lt,lt+ltab[LTCODES+l],ltab[1]+les);
  417.         }
  418.         tupd(ltab,LTCODES,MAXLT,LTSTEP,l);
  419.         if (ltab[LTCODES+l]==LCUTOFF) les-=LTSTEP<les?LTSTEP:les-1; 
  420.         if (l==SLCODES-1) l=LENCODES-1;
  421.         else if (l>=SLCODES) {
  422.         i=ac_threshold_val(LLLEN);
  423.         ac_in(i,i+1,LLLEN);
  424.         l=((l-SLCODES)<<LLBITS)+i+SLCODES-1;
  425.         }
  426.         l+=3;
  427.         if (ccnt<POSCODES) {
  428.         ccnt+=l;
  429.         if (ccnt>POSCODES) ccnt=POSCODES;
  430.         }
  431.         swd_dpair(l,p);                
  432.     }
  433.     else {
  434.         ac_in(i,i+1,i+1);
  435.         flush();
  436.         asc_cleanup();
  437.         return;
  438.     }
  439.     }
  440. }
  441.  
  442.  
  443.